package datastructure;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author lzy
 * @create 2019-11-20 下午3:00
 */
public class Chapter5_12 {
    public static void main(String[] args) {
        int[] array = {4, 1, 2, 2, 5, 1, 4, 3};
        final int[] lostNumber = findLostNumber(array);
        System.out.println(Arrays.toString(lostNumber));
    }

    public static int[] findLostNumber(int[] array) {
        //1.用于存储２个出现奇数次的整数
        int[] result = new int[2];
        //第１次进行整体异或运算
        int xorResult = 0;
        for (int i = 0; i < array.length; i++) {
            xorResult = xorResult ^ array[i];
        }
        //如果计算异或运算的结果为０，说明输入的数组不符合题目要求
        if (xorResult == 0) {
            return null;
        }

        //确定２个整数的不同位，以此来做分组
        int separator = 1;
        while (0 == (separator & xorResult)) {
            separator <<= 1;
        }

        //第２次分组进行异或运算
        for (int i = 0; i < array.length; i++) {
            if ((separator & array[i]) == 0) {
                result[0] ^= array[i];
            } else {
                result[1] ^= array[i];
            }
        }

        return result;
    }
}
